675D - Tree Construction - CodeForces Solution

#include <bits/stdc++.h>
using namespace std ;

#define ll long long
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

const int N = 2e5 + 1 , MOD = 1e9 + 7 , p = 37 ;

int n , a[N] ;

struct node {
	int key ;
	node *l ;
	node *r ;
} ;

node* newNode(int val) {
	struct node* temp
        = (struct node*)malloc(sizeof(struct node));
    temp->key = val ;
    temp->l = temp->r = NULL;
    return temp;
}

node* minVal(node* root) {
	node* cur = root ;
	while (cur && cur->l != NULL) {
		cur = cur->l ;
	}
	return cur ;
}

node* insert(node* root, int val , int parent) {
	if (root == NULL) {
		if (parent != -1) {
			cout << parent << ' ' ;
		} 
		return newNode(val) ;
	}
	if (root->key > val) {
		root->l = insert(root->l , val , root->key) ;
	} else {
		root->r = insert(root->r , val , root->key) ;
	}
	return root ;
}

node* remove(node* root, int val) {
	if (root == NULL) return root ;
	if (root->key > val) {
		root->l = remove(root->l , val) ;
	} else 
	if (root->key < val) {
		root->r = remove(root->r , val) ;
	} else {
		if (root->l == NULL) {
			node* cur = root->r;
			free(root) ;
			return cur ;
		} else 
		if (root->r == NULL) {
			node* cur = root-> l ;
			free(root) ;
			return cur ;
		}
		node* cur = minVal(root->r) ;
		root->key = cur->key ;
		root->r = remove(root->r , cur->key) ;
	}
	return root ;
}

bool find(node* root , int val) {
	if (root == NULL) return 0 ;
	if (root->key > val) {
		return find(root->l , val) ;
	} else 
	if (root -> key < val) {
		return find(root->r , val) ;
	} else {
		return 1 ;
	}
	return 0 ;
}

void solve() {
	cin >> n ;
	for (int i = 1 ; i <= n ; i++) {
		cin >> a[i] ;
	} 
	vector<int> l(n + 1 , 0) , r(n + 1 , 0) ;
	set<pair<int,int>> s ;
	s.insert({a[1] , 1}) ;
	for (int i = 2 ; i <= n ; i++) {
		auto it = s.lower_bound({a[i] , 0}) ;
		while (1) {
			if (it != s.end()) {
				if (it->first > a[i]) {
					if (!l[it->second]) {
						l[it->second] = i ;
						cout << it->first << ' ' ;
						break ;
					}
				} else {
					if (!r[it->second]) {
						r[it->second] = i ;
						cout << it->first << ' ' ;
						break ;
					}
				}
			}
			if (it == s.begin()) break ;
			it-- ;
		}
		s.insert({a[i] , i}) ;
	}
}

int main() {
	ios::sync_with_stdio(false) ;
	cin.tie(0) ;
	int test = 1 ;
	// cin >> test ;
	for (int i = 1 ; i <= test ; i++)
		solve() ;
}